1. Field of the Invention
The present invention relates generally to spatial searches and, more specifically, to spatial searches ranked according to weighted distances.
2. Description of the Related Art
Spatial searches, or searches in which the search results depend upon geographic location, have a variety of uses. For example, users may query a spatial-search engine for pizza parlors near the user's location (requesting, for instance “pizza near zip code 78701”), and a spatial search responsive to that query may return one or more pizza parlors ranked based on the distance between the pizza parlor and the reference location of zip code 78701. Similar queries may occur in scenarios in which a user is planning a vacation and searches for, for example, airports near a hotel in which the user has booked a room, or in scenarios in which content for a web page is selected based on geographic location, for example, an advertisement for a pizza parlor may be selected for display to a user based on the distance between the user's location (if the user opts to disclose their location) and the location of several pizza parlors seeking to advertise. Spatial searches, thus, are often performed when the relevancy of results depends on distance from some reference location.
In some cases, it can be helpful to rank search results based on both distance and other factors. For example, a user may search for airports near a reference location that is both relatively close to a small municipal airport and somewhat further from a large international airport. The large airport is more likely to be relevant to the searcher than the small municipal airport, even though the large airport is further away from the reference location about which the spatial search is based. Thus in this example, relevance may depend both on distance and size. To account for scenarios in which both distance and some other attribute affect the relevance of search results, some spatial searches are based on a weighted distance, or a value that is a function of both distance and some attribute or attributes. Weighted distances often cause farther geographic items to rank higher than closer geographic items when the weighting is heavy enough to overcome the difference in distance.
For a variety of reasons, spatial searches based on weighted distances are difficult to implement. Weighted-distance spatial searches often include evaluating a relatively large number of candidate items as potential search results because heavy weightings can cause relatively distant items to be responsive to a query. For instance, in the airport example, some spatial searches may include evaluating every airport on the continent in case an airport several thousand miles away has a particularly heavy weighting causing that airport to have the closest weighted distance. Evaluating a large number of candidate items often slows the search and diminishes the usefulness of spatial searches.